package com.cn.codebrush.字符串;

/**
 * @Author Boolean
 * @Date 2022/4/26 14:34
 * @Version 1.0
 */
public class No5最长回文子串 {
    public static void main(String[] args) {
        String s = "babad";
        String s1 = "bbb";
        System.out.println(longestPalindrome(s1));
    }


    /**
     * 动态规划
     * 二维数组
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        String res = s.substring(0,1);
        int n = s.length();
        if(n < 2){
            return s;
        }else if(n == 2 && s.charAt(0) == s.charAt(1)){
            return s;
        }

        boolean[][] dp = new boolean[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i) == s.charAt(j) && (j-i<=2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    res = s.substring(i,j+1).length()>res.length()?s.substring(i,j+1):res;
                }
            }
        }
        return res;
    }
}
